package cn.willbj.brief.hootl.sort.demo;

import java.util.Arrays;

public class Demo04 {
	public static void main(String[] args) {
		int[] arr = {3,7,2,1,9,5,8};
		
		int[] qSort = qSort(arr);
		
		System.out.println(Arrays.toString(qSort));
	}
	
	public static int[] qSort(int[] arr) {
		int[] copyOf = Arrays.copyOf(arr, arr.length);
		qSortBiz(copyOf, 0, copyOf.length-1);
		return copyOf;
	}
	
	public static void qSortBiz(int[] copyOf, int left, int right) {
		if (left >= right) {
			return;
		}
		int param = parambiz(copyOf,left,right);
		qSortBiz(copyOf, left, param-1);
		qSortBiz(copyOf, param+1, right);
	}

	private static int parambiz(int[] copyOf, int left, int right) {
		int param = left;
		int index = param + 1;
		
		for (int i = index; i <= right; i++) {
			if (copyOf[i] < copyOf[param]) {
				swap(copyOf,index,i);
				index++;
			}
		}
		swap(copyOf, param, index-1);
		return index-1;
	}

	private static void swap(int[] arr, int index, int i) {
		if (index == i) {
			return;
		}
		int temp = arr[index];
		arr[index] = arr[i];
		arr[i] = temp;
	}
}
